package com.leetcodehot.problems;

import java.util.ArrayList;
import java.util.List;

public class problems131 {
    /**
     * 思考：首先题目要求分割，那么就有一种选择，我们选择从哪个地方分割
     * 然后检验是否回文
     */
    /**
     * 做法一：答案视角，选择哪一个逗号
     */
    /*private final List<List<String>> ans = new ArrayList<>();
    private final List<String> path = new ArrayList<>();
    private String s;

    public List<List<String>> partition(String s) {
        this.s = s;
        dfs(0);
        return ans;
    }

    private void dfs(int i) {
        if (i == s.length()) {
            ans.add(new ArrayList<>(path));
            return;
        }

        for (int j = i; j < s.length(); j++) {
            if (isPalindrome(i, j)) {
                path.add(s.substring(i, j + 1));
                dfs(j + 1);
                path.remove(path.size() - 1);
            }
        }
    }

    private boolean isPalindrome(int left, int right) {
        while (left < right) {
            if (s.charAt(left++) != s.charAt(right--)) {
                return false;
            }
        }
        return true;
    }*/

    /**
     * 输入视角，第i个逗号 选择与不选
     */
    private final List<List<String>> ans = new ArrayList<>();
    private final List<String> path = new ArrayList<>();
    private String s;

    public List<List<String>> partition(String s) {
        this.s = s;
        dfs(0, 0);
        return ans;

    }

    //start表示子串从哪来说
    private void dfs(int i, int start) {
        if (i == s.length()) {
            ans.add(new ArrayList<>(path));
            return;
        }

        //不选
        if (i < s.length() - 1) {
            dfs(i + 1, start);
        }

        //选
        if (isPalindrome(start, i)) {
            path.add(s.substring(start, i + 1));
            dfs(i + 1, i + 1);
            path.remove(path.size() - 1);
        }
    }

    private boolean isPalindrome(int left, int right) {
        while (left < right) {
            if (s.charAt(left++) != s.charAt(right--)) {
                return false;
            }
        }
        return true;
    }
}
